package ljl.alg.jianzhioffer.round2;

import commons.ListNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
* 1. 放到数组里，逆序
* 2. 翻转链表
* 3. 递归
*
* 路飞的两个解法：
* 4. 辅助栈
* 5. 递归填充一个 list 再倒序输出
* 这两个没啥本质区别，还是我这三个区别大点，我猜
* */
public class _06_reverse_print_list {
    
    // very slow
    public int[] reversePrint1(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        Collections.reverse(list);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    
    // faster
    public int[] reversePrint2(ListNode head) {
        ListNode prev = null;
        int i = 0;
        while (head != null) {
            i++;
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        int[] res = new int[i];
        int j = 0;
        while (prev != null) {
            res[j++] = prev.val;
            prev = prev.next;
        }
        return res;
    }
    
    /*
    * 递归确实不好写
    * 好在最后蒙对了
    * */
    int[] res;
    int total, i;
    public int[] reversePrint(ListNode head) {
        if (head != null) {
            total++;
            reversePrint(head.next);
            res[i++] = head.val;
        }
        if (res == null) res = new int[total];
        
        return res;
    }
}
